package com.duoduo.剑指Offer;

import com.duoduo.TreeNode;

/**
 * @program: algorithm
 * @description: 树的子结构11
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * <p>
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 * <p>
 * 例如:
 * 给定的树 A:
 * <p>
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 * 给定的树 B：
 * <p>
 *    4 
 *   /
 *  1
 * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 * <p>
 * 示例 1：
 * <p>
 * 输入：A = [1,2,3], B = [3,1]
 * 输出：false
 * 示例 2：
 * <p>
 * 输入：A = [3,4,5,1,2], B = [4,1]
 * 输出：true
 * @author: chaidl  ！
 * @create: 2022-05-23 22:39
 */
public class 树的子结构11 {
	public boolean isSubStructure(TreeNode A, TreeNode B) {
		//		首先判断如果两个数有一个空，返回false
		if (A == null || B == null) {
			return false;
		}
		//	再判断B是A的子树的条件。
		return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
	}
	
	private boolean recur(TreeNode a, TreeNode b) {
		//只要是到了这里的时候，肯定有一个不为空
		//1.如果b为空，那么肯定是子树
		if (b == null) {
			return true;
		}
		if (a == null || a.val != b.val) {
			return false;
		}
		//到了这里说明ab相等，再去判断
		//他们的左右子树
		return recur(a.left, b.left) && recur(a.right, b.right);
	}
}
